package com.whitedust.top80;

import com.whitedust.structure.ListNode;

import java.util.List;

/**
 *
 * @author A
 * @since 2025/11/15 23:29
 */

public class Top74 {
    public boolean isPalindrome(ListNode head) {
        ListNode list2 = getMid(head);
        ListNode head2 = reverseList(list2);
        while (head != null && head2 != null) {
            if (head.val != head2.val) return false;
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }

    private ListNode getMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        if (pre != null) {
            pre.next = null;
        }
        return slow;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
